package com.Expression;

/**
 * 计算前缀表达式
 */
public class Calculator {
    public static void main(String[] args) {
        String expression = "700+20*2-4";
        //分别创建数栈和符号栈
        int result = getResult(expression);
        System.out.println(expression + "=" + result);

    }

    /**
     *  思路：
     *  通过Index索引将表达式进行遍历
     *  扫描到数字时入数字栈，符号则如符号栈
     *  符号栈为空                        -> 直接入栈
     *  当前入栈符号优先级比栈顶符号优先级高   -> 直接入栈
     *  入栈符号优先级小于或等于栈顶符号优先级 -> 从数栈中弹出2个数，符号栈中弹出一个符号进行运行，将运算结果压入栈中
     *  当遍历完表达式时，顺序从数栈和符号栈中出栈进行计算，最后再数栈中的数字即为运算结果
     *
     *  缺陷：
     * 1.减法和除法顺序影响计算结果（待改进
     * @param expression 计算前缀表达式
     * @return
     */
    public static int getResult(String expression) {
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);

        int index = 0;  //扫描表达式的变量
        int num1 = 0;   //接收弹出的两个数字
        int num2 = 0;
        int oper = 0;   //接收弹出的操作符
        int result = 0; //保存弹出数字和运算符的计算结果
        char ch = ' ';  //保存扫描到的字符
        String keepNum = ""; //用于拼接多位数字符串
        while (index < expression.length()) {
            ch = expression.charAt(index);
            //判断ch是符号还是数字
            if (operStack.isOper(ch)) {
                if (!operStack.isEmpty()) {
                    //每次入栈时判断符号优先级
                    if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        result = numStack.cal(num1, num2, oper);
                        //将运算结果和当前运算符入栈
                        numStack.push(result);
                        operStack.push(ch);
                    } else {
                        operStack.push(ch);
                    }
                } else {
                    //判断当前符号栈是否为空，是则直接入栈
                    operStack.push(ch);
                }
            } else {
                //如果是数则将数入栈
                //将'1'-'0'= 1,字符1和字符0的差值即整数1
                keepNum += ch;
                //如果ch已经是最后一个数了则直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    //先判断后一位是否为数字，如果是则index后移一位
                    while (!operStack.isOper(expression.charAt(index + 1))) {
                        keepNum += expression.charAt(++index);
                    }
                    numStack.push(Integer.parseInt(keepNum));
                    //清空KeepNum
                    keepNum = "";
                }
            }
            index++;
        }

        //将扫描完表达式以后，顺序从数栈和符号栈中出栈进行运算，如果符号栈为空时，即运算结束（留在数栈中的数字即为结果
        while (!operStack.isEmpty()) {
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            result = numStack.cal(num1, num2, oper);
            //将运算结果入栈
            numStack.push(result);
        }
        return result;
    }

    /**
     * 中缀表达式转后缀表达式
     * @param prefixExp
     * @return
     */
    public String prefixToSuffix(String prefixExp){
        return null;
    }
}
